package 字节;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class 数组的第K大 {
    List<Integer> list=new ArrayList<>();


    public static void main(String[] args) {

        int[] a={1,3,5,4,2};
        int n=5;
        int K=4;
        System.out.println(findKth(a,5,K));

    }
    static int findKth(int[] a,int n,int K){
          int target=n-K;
          int left=0;
          int right=n-1;
          while (true){
              int index=getIndex(a,left,right);
              if(index==target) return a[index];
              else if(index<target) left=index+1;
              else if(index>target) right=index-1;
          }
    }

    static int getIndex(int[] a,int left,int right){
        Random random=new Random();
        int index = random.nextInt(right-left+1)+left;
        int compare=a[index];
        int t=a[left];
        a[left]=compare;
        a[index]=t;
        while (left<right){
            while (left<right&&a[right]>=compare){
                right--;
            }
            a[left]=a[right];
            while (left<right&&a[left]<=compare){
                left++;
            }
            a[right]=a[left];
        }
        a[left]=compare;
        return left;
    }


}
